package com.zklh.leetcode.other.problem62;

/**
 * 尝试每一种走法,
 */
class Solution implements SolutionInterface{
    private int pathNums = 0;
    @Override
    public int uniquePaths(int m, int n) {
        move(0,0,m,n);
        return pathNums;
    }
    /**
     *
     * 定义移动方法,定义为移动到某一点每次移动一步
     * 递归方法, 动态规划的体现, 将移动到指定位置的问题, 分解为移动一步的问题
     * 在移动过程中对不可能到达目的地的路线pass掉
     * @param x
     * @param y
     * @param m
     * @param n
     */
    private void move(int x, int y, int m, int n){
        // 如果当前越界, 表示不能到达终点,不计数
        if(x > m || y > n){
            return;
        }else if(x == m && y == n){// 表示当前就是一条路径的终点, 计数+1
            pathNums++;
            return;
        }
        /* 每次移动一步,保证不会出现路线重复 */
        // 在x上移动一步
        move(x+1,y,m,n);
        // 在纵向移动一步
        move(x,y+1,m,n);
    }


    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.uniquePaths(23, 12));
    }

}
